package com.tgy.algorithm.base.morris;

import com.tgy.algorithm.base.other.BiTreeNode;

public class _morris {

    public static BiTreeNode general() {

        /**
         *             0
         *         1       2
         *     3      4
         */
        BiTreeNode root = new BiTreeNode(0);

        root.left = new BiTreeNode(1);
        root.right = new BiTreeNode(2);

        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(4);

        return root;
    }

    public static void morris(BiTreeNode root) {


        BiTreeNode node = root;
        System.out.println(node.value);
        BiTreeNode nextNode = null;
        while (node != null) {
            if (node.left != null) {
                nextNode = node.left;
                while (nextNode != null && nextNode.right != null && nextNode.right != node) {
                    nextNode = nextNode.right;
                }

                if (nextNode.right == null) {
                    nextNode.right = node;
                    node = node.left;
                    System.out.println(node.value);
                    continue;
                }else {
                    nextNode.right = null;
                }
            }

            node = node.right;
            if (node != null) {
                System.out.println(node.value);
            }

        }

    }

    public static void main(String[] args) {
        BiTreeNode root = general();
        morris(root);
    }
}
